#include <iostream>
#include "graphtypes.h"
#include "GraphOriented.h"
#include "GraphFlow.h"
#include <stack>
#include <queue>

using namespace std;

GraphOriented::GraphOriented() { //cerr<<"Constructeur par défaut de GraphOriented"<<endl;
}
GraphOriented::GraphOriented(summit_t n, edges_t m) : Graph::Graph(n,m) { //cerr<<"Constructeur paramétré de GraphOriented"<<endl;
}
GraphOriented::~GraphOriented() {}

void GraphOriented::updateLevelGraph(const GraphFlow &g, vector<summit_t> * path, flow_t delta)
{
  vector<summit_t> * neighbours;
  stack<summit_t> s_stack;
  summit_t s_temp, n_temp;

  if (path==NULL)
  {
    queue<summit_t> s_queue;
    summit_t * level = new summit_t [summit_nb];
    for (summit_t i=0; i<summit_nb; i++)
    {
      level[i]=(summit_t)-1;
      for (size_t j=0; j<summit_nb; j++)
      {                                  //On déconnecte tous les arcs
	deconnect(i,j);
      }
    }
    s_queue.push(0); //Ajout du sommet source à la liste
    level[0]=0;
    while (not s_queue.empty())
    {
      s_temp = s_queue.front(); s_queue.pop();
      if (s_temp == summit_nb-1)
	break;
      neighbours = g.getNeighbours(s_temp);
      for (size_t k(0); k<neighbours->size(); k++)
      {
	n_temp=neighbours->at(k);
	if (((level[n_temp]==(summit_t)-1) && ((level[summit_nb-1]==(summit_t)-1) || (level[n_temp]<level[(summit_t)summit_nb-1]))) || (level[s_temp]+1==level[n_temp]))
	{
	  if ((g.getCapacity(s_temp,n_temp)>g.getFlow(s_temp,n_temp))) //Il faut aussi que l'arc ne soit pas saturé
	  {
	    if (level[n_temp]==(summit_t)-1) //Si sommet jamais vu
	    {
	      s_queue.push(n_temp); //Pour qu'il apparaisse une fois dans la file
	      level[n_temp]=level[s_temp]+1;
	    }
	    connect(s_temp,n_temp);
	  }
	}
      }
      delete neighbours;
    }
    delete [] level;
  }

  else
  {    
    for (size_t i=1; i<path->size(); i++)
    {
      if (g.getCapacity(path->at(i-1),path->at(i))==g.getFlow(path->at(i-1),path->at(i))) //Arc saturé
      {
	deconnect(path->at(i-1),path->at(i));
	/*neighbours = getNeighbours(path->at(i-1));
	if ((not neighbours) || (neighbours->size()==0 )) //Cul de sac, car aucun voisin sortant
	{
	  s_stack.push(path->at(i-1));
	}
        if (neighbours)
	{
	  delete neighbours; neighbours=NULL;
	  }*/
      }
    }
  }

  /*vector<summit_t> * parents;
  while (not s_stack.empty())
  {
    s_temp = s_stack.top(); s_stack.pop();
    parents = isNeighbourOf(s_temp);
    if (parents)
    {
      for (size_t i=0; i<parents->size(); i++)
      {
	neighbours = getNeighbours(parents->at(i));
	if (neighbours && neighbours->size()>0)
	{
	  deconnect(parents->at(i),s_temp);
	  if ((neighbours->size()==1))        //Il ne possédait qu'un voisin sortant (désormais cul de sac)
	    s_stack.push(parents->at(i));     //Donc on le rajoute à la liste des sommets
	  delete neighbours;
	}
      }
      delete parents;
    }  
    }*/
}

void GraphOriented::updateCapacityScallingGraph(const GraphFlow &g, flow_t max_cap, vector<summit_t> * path)
{
  if (path==NULL) //Il faut tout reconstruire
  {
    for (summit_t i=0; i<summit_nb; i++)
    {
      for (summit_t j=0; j<summit_nb; j++)
      {
	deconnect(i,j);
      }
    }

    bool * seen = new bool [summit_nb];
    for (int k(0); k<summit_nb; k++)
    {
      seen[k]=false;
    }
    vector<summit_t> * neighbours;
    queue<summit_t> * s_queue = new queue<summit_t>;
    summit_t s_temp, n_temp;

    s_queue->push(0); //Ajout du sommet source à la liste
    seen[0] = true;
    while ((not s_queue->empty()))
    {
      s_temp = s_queue->front(); s_queue->pop(); //Récupère le premier élément de la file, puis le supprime
      neighbours = g.getNeighbours(s_temp);
      for (size_t k(0); k<neighbours->size(); k++)
      {
	n_temp=neighbours->at(k);
	if ((g.areConnected(s_temp,n_temp)) && ((g.getCapacity(s_temp,n_temp)-g.getFlow(s_temp,n_temp))>= max_cap))
	{
	  connect(s_temp,n_temp);
	  if (not seen[n_temp])
	  {
	    s_queue->push(n_temp);
	    seen[n_temp]=true;
	  }
	}
      }
      delete neighbours;
    }
    delete s_queue;
    delete [] seen;
  }

  else
  {
    summit_t u,v;
    u=path->at(0);
    for (size_t i=1; i<path->size(); i++) //Mise à jour du flot
    {
      v=path->at(i);
      if (g.getCapacity(u,v)<=g.getFlow(u,v))
	deconnect(u,v);
      u=v;
    }
  }
}
